package year2023.dp;

public class Code05_BagDP {


    //bag 背包容量，不能超过载重
    //返回：不超重的情况下，能够得到的价值
    public static int maxValue(int[] w, int[] v, int bag){
        if (w == null || v == null || w.length != v.length || w.length ==0){
            return 0;
        }

        return process(w,v,0,bag);
    }


    //暴力递归
    public static int process(int[] w, int[] v, int index, int rest){
        if (rest < 0){
            return -1;
        }
        if (index == w.length){
            return 0;
        }
        //有货，index位置的货
        //bag有空间
        //1. 不要当前的货
        int p1 = process(w, v, index+1, rest);

        //要当前的货
        int p2 = 0;
        int next = process(w, v, index + 1, rest - w[index]);
        if (next != -1){
            p2 = v[index] + next;
        }

        return Math.max(p1, p2);

    }

    //DP

    public static int dp(int[] w, int[] v, int bag){
        int N = w.length;
        int[][] dp = new int[N+1][bag + 1];
        if (w == null || v == null || w.length != v.length || w.length ==0){
            return 0;
        }
        //index 0 ~ N
        //rest 负数 ~ bag
        for (int index = N-1; index >= 0 ; index--) {
            for (int rest = 0; rest <= bag ; rest++) {
                int p1 = dp[index + 1][rest];
                //要当前的货
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1){
                    p2 = v[index] + next;
                }
                dp[index][rest]=Math.max(p1, p2);


            }
        }
        return dp[0][bag];

    }






    public static void main(String[] args) {
        int[] w = {3, 2, 4, 7};
        int[] v = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(maxValue(w,v,bag));
        System.out.println(dp(w, v, bag ));
    }

}
